package com.example.demo.leetcode;

import com.example.demo.leetcode.zuocheng.graph.Edge;
import com.example.demo.leetcode.zuocheng.graph.Node;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author xujimou
 * @version 2.0
 * @Description
 * @date 2021/8/12 14:14
 */
public class test {


    public  static Node initNode(){

        HashMap<String,Node> map = new HashMap<>();
        String [][] arr ={{"A","B","1"},{"A","C","2"},{"B","D","4"},{"C","D","2"}};

        for(int i =0 ;i<arr.length;i++){

            String [] temp=arr[i];
            Node from = map.get(temp[0]+"") == null ?  new Node(temp[0]+"") : map.get(temp[0]+"");
            Node to = map.get(temp[1]+"") == null ?  new Node(temp[1]+"") : map.get(temp[1]+"");
            from.out++;
            to.in++;

            Edge edge = new Edge(Integer.parseInt(temp[2]),from,to);

            from.edges.add(edge);
            from.nexsts.add(to);

            map.put(from.value,from);
            map.put(to.value,to);
        }

        return map.get("A");
    }

    public static Map<Node,Integer> djstla(){

        Node node = initNode();

        Map<Node,Integer> map = new HashMap<>();
        Set<Node> selectSet = new HashSet<>();
        map.put(node,0);

        Node start = getMinInstanceNode(map, selectSet);
        while(start != null){
            Integer distance = map.get(start);
            for(Edge edge : start.edges){
                if(!map.containsKey(edge.to)){
                    map.put(edge.to, edge.weight);
                }else{
                    Integer oldDistance = map.get(edge.to);
                    Integer newDistance = distance + edge.weight;
                    map.put(edge.to, Math.min(oldDistance,newDistance));
                }
            }
            start = getMinInstanceNode(map, selectSet);
        }
        return map;
    }

    public static Node getMinInstanceNode(Map<Node,Integer> map,Set<Node> selectSet){

        Node node = null;
        int distance = Integer.MAX_VALUE;
        for(Map.Entry<Node,Integer> entry: map.entrySet()){
            if(!selectSet.contains(entry.getKey()) && entry.getValue()<distance){
                distance = entry.getValue();
                node = entry.getKey();
                selectSet.add(entry.getKey());
            }
        }
        return node;
    }






    public static void main(String[] args) {
        Map<Node, Integer> map = djstla();

        for(Map.Entry<Node,Integer> entry : map.entrySet()){
            System.out.println(entry.getKey().value+":"+entry.getValue());
        }

    }


}
